package 图.无向图;

import 抽象数据类型.Bag;
import 抽象数据类型.Graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @descripition:
 * @author: yangwk37982
 * @date: 2021/7/26 15:09
 */
public class 找出图的连通分量 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 2, 0, 3, 4, 5, 6, 7, 9, 10, 11, 12};
        int[] arr2 = {6, 0, 0, 5, 5, 3, 4, 4, 8, 11, 9, 12, 9};
        Graph G = new Graph(arr1.length);
        G.addGraph(arr1, arr2);
//        CC cc = new CC(G);
        CC cc = new CC();
        cc.bfs(G);
        int M = cc.count;
        System.out.println(M + "components");
        Bag<Integer>[] components = new Bag[M];
        for (int i = 0; i < M; i++) {
            components[i] = new Bag<>();
        }
        for (int v = 0; v < G.V(); v++) {
            components[cc.id(v)].add(v);
        }
        for (int i = 0; i < M; i++) {
            for (Integer v : components[i]) {
                System.out.print(v + "\t");
            }
            System.out.println();
        }
    }

    public static class CC {
        private  boolean[] marked;
        private  int[] id;
        private int count;

        public CC(Graph G) {
            marked = new boolean[G.V()];
            id = new int[G.V()];
            for (int s = 0; s < G.V(); s++) {
                if (!marked[s]) {
                    dfs(G, s);
                    count++;
                }
            }
        }
        public CC() {

        }
        private void dfs(Graph G, int v) {
            marked[v] = true;
            id[v] = count;
            for (Integer w : G.adj(v)) {
                if (!marked[w]) {
                    dfs(G, w);
                }
            }
        }
        private void bfs(Graph G){
            Queue<Integer> queue = new LinkedList<>();
            marked = new boolean[G.V()];
            id = new int[G.V()];
            for (int v = 0; v < G.V(); v++) {
                if (!marked[v]) {
                    queue.offer(v);
                    while (!queue.isEmpty()) {
                        Integer poll = queue.poll();
                        for (Integer s : G.adj(poll)) {
                            if (!marked[s]) {
                                id[s] = count;
                                marked[s] = true;
                                queue.offer(s);
                            }
                        }
                    }
                    count++;
                }
            }
        }

        public boolean connected(int v, int w) {
            return id[v] == id[w];
        }

        public int id(int v) {
            return id[v];
        }

        public int count() {
            return count;
        }
    }
}
